package com.example.linked;

/**
 * 给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,
 * 并且每个节点只能存储一位数字。
 * 将两个数相加，并以相同形式返回一个表示和的链表
 * 假设除了数字 0之外，这两个数都不会以0开头。
 */
public class Leetcode2_addNum {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);

        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(3);
        l2.next.next.next = new ListNode(1);
        System.out.println(addTwoNumbers3(l1, l2));
    }

    /**
     * 暴力解法：
     * 遍历两个链表使⽤用数学思维分别将他们转成整数
     * 对两个整数进⾏行行求和得到sum
     * 将sum按照数学思维再转成链表
     * ⼿手动测试：
     * 若超过语⾔言⽀支持的数据类型范围，则报错
     * 解决办法：BigInteger
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //把链表转成数字，注意次序为逆序
        long l1Value = 0;
        int digit = 0;
        while (l1 != null) {
            int pow = (int) Math.pow(10, digit);
            l1Value += (long) l1.val * pow;
            digit++;
            //链表指向下⼀一个节点
            l1 = l1.next;
        }
        long l2Value = 0;
        digit = 0;
        while (l2 != null) {
            int pow = (int) Math.pow(10, digit);
            l2Value += (long) l2.val * pow;
            digit++;
            //链表指向下⼀一个节点
            l2 = l2.next;
        }
        //创建⼀一个新链表，头部为空节点
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        //数字相加
        long sum = l1Value + l2Value;
        if (sum == 0) {
            head = new ListNode(0);
            return head;
        }
        //数字再转成链表
        while (sum > 0) {
            //每次取当前最低位
            int val = (int) (sum % 10);
            //移除最低位
            sum = sum / 10;
            ListNode node = new ListNode(val);
            //插⼊入链表尾部
            cur.next = node;
            //链表尾部指针移动
            cur = cur.next;
        }
        return head.next;
    }

    /**
     * 暴力解法：
     * 若超过语⾔言⽀支持的数据类型范围，则报错
     * 解决办法：使用BigInteger
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        //把链表转成数字，注意次序为逆序
        java.math.BigInteger l1Value = java.math.BigInteger.valueOf(0);
        int digit = 0;
        while (l1 != null) {
            java.math.BigInteger carry =
                    java.math.BigInteger.valueOf(10).pow(digit);
            l1Value =
                    l1Value.add(carry.multiply(java.math.BigInteger.valueOf(l1.val)));
            digit++;
            l1 = l1.next;
        }
        java.math.BigInteger l2Value = java.math.BigInteger.valueOf(0);
        digit = 0;
        while (l2 != null) {
            java.math.BigInteger carry =
                    java.math.BigInteger.valueOf(10).pow(digit);
            l2Value =
                    l2Value.add(carry.multiply(java.math.BigInteger.valueOf(l2.val)));
            digit++;
            l2 = l2.next;
        }
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        //数字相加，然后再转成链表
        java.math.BigInteger sum = l1Value.add(l2Value);
        if (sum.compareTo(java.math.BigInteger.valueOf(0)) == 0) {
            head = new ListNode(0);
            return head;
        }
        while (sum.compareTo(java.math.BigInteger.valueOf(0)) > 0) {
            int val = sum.mod(java.math.BigInteger.valueOf(10)).intValue();
            sum = sum.divide(java.math.BigInteger.valueOf(10));
            ListNode node = new ListNode((int) val);
            cur.next = node;
            cur = cur.next;
        }
        return head.next;
    }

    /**
     * 最优解：数学思维解法
     * 1.遍历两个链表
     * 2.对应位置的节点数值相加
     * 3.将计算结果插⼊入新链表尾部
     * ⼤大于10，则进位，将进位加到下个节点
     *
     * 边界问题
     * 两个链表边界：next==null
     * 细节问题
     * 两个链表⻓长度不不⼀一致，短链表⾼高位视为0
     * 链表最⾼高位发⽣生进位，结果链表需要增加⼀一个节点存放进位数字
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers3(ListNode l1, ListNode l2) {
        ListNode p = l1, q = l2; // 原链表的两个遍历指针
        ListNode resultHead = new ListNode(-1); // 结果链表的头结点head
        ListNode curr = resultHead; // 结果链表的遍历指针，代表当前操作的节点
        int carry = 0; // 进位
        // 1.遍历两个链表
        while (p != null || q != null) { // 以⻓长链表为准
            // 获取当前节点的值：链表较短，已⽆无节点，取0
            int x = p != null ? p.val : 0;
            int y = q != null ? q.val : 0;
            // 2.对应位置的节点数值相加
            int sum = x + y + carry;
            carry = sum / 10; // 如何得到进位：和对10求整，得到此次计算的进位
            int num = sum % 10; // 存放到新链表节点中的数值
            // 3.将计算结果插⼊入新链表尾部
            curr.next = new ListNode(num); // 创建新节点
            curr = curr.next;
            p = p == null ? p : p.next;
            q = q == null ? q : q.next;
        }
        if (carry > 0) { // 处理理进位节点
            curr.next = new ListNode(carry);
        }
        return resultHead.next;
    }

}

//class ListNode {
//    int val; // 数据域
//    ListNode next; // 指针域，指向下⼀一个节点
//    ListNode(int x) {
//        val = x;
//    }
//}
